package com.lwt.codetop.binaryTree;
// 199. 二叉树的右视图

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * 思路一：bfs，拿到每一层，然后每一层取出末尾元素
 * 思路二：dfs: 要拿到每一层的右边的元素（每一层只拿一个），我们采用 根右左 的遍历顺序
 *             然后只保留第一个数：如何确保保留第一个数呢-->标记数组，判断该层是否有用过了
 */
public class BinaryTreeRightSideView {
    public static void main(String[] args) {
        // 构建测试用例
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.right = new TreeNode(5);
        root.right.right = new TreeNode(4);

//        List<Integer> res = rightSideView(root);
//        System.out.println(res);

        List<Integer> res = new ArrayList<>();
        boolean[] st = new boolean[110];
        dfs(root, 1, res, st);
        System.out.println(res);

    }

    /**
     * bfs求二叉树的右视图
     * @param root
     * @return
     */
    private static List<Integer> rightSideView(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) return res; // 特判
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        while (!q.isEmpty()){
            int len = q.size();
            List<Integer> ceng = new ArrayList<>();
            for (int i = 0; i < len; i++) {
                TreeNode node = q.poll();
                ceng.add(node.val);
                if(node.left != null) q.add(node.left);
                if(node.right != null) q.add(node.right);
            }
            res.add(ceng.get(ceng.size() - 1));
        }
        return res;
    }
    /**
     * dfs求二叉树的右视图
     * @param root
     * @return
     */
    private static void dfs(TreeNode root, int depth, List<Integer> res, boolean[] st) {
        if(root == null) return;
        if(st[depth] == false){
            st[depth] = true;
            res.add(root.val);
        }
        dfs(root.right, depth + 1, res, st);
        dfs(root.left, depth + 1, res, st);
    }

}
